package com.example.array.doublepointer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Leetcode169_MajorityElement {
    public static void main(String[] args) {

        System.out.println(majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));

    }

    /**
     * 解法一:
     * 排序，然后用双指针统计各个数字出现的次数，有大于 2/n的就返回该元素
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int begin = 0, end = 1, count = 1;
        while (begin <= nums.length / 2 && end < nums.length ) {
            if (nums[begin] == nums[end]) {
                count++;
                ++end;
            } else {
                if (count > nums.length / 2) {
                    return nums[begin];
                } else {
                    begin = end;
                    ++end;
                    count = 1;
                }
            }
        }

        // 最后一次的元素个数需要单独判断
        if (count > nums.length / 2) {
            return nums[begin];
        }
        System.out.println(begin +"  " + end);
        return -1;
    }

    /**
     * 解法二:使用map统计
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            int count = map.getOrDefault(num, 0) + 1;
            //超过一半，则直接返回
            if (count > nums.length / 2) {
                return num;
            }
            map.put(num, count );
        }
        return -1;
    }

    /**
     * 摩尔投票法
     *
     * 用球类运动中的盯人战术，只要两个选票数字不一样，就相互盯死
     * 那么最后剩下的没被盯住肯定是那个超过半数的选票
     * @param nums
     * @return
     */
    public static int majorityElement3(int[] nums) {
        int result = nums[0];
        int times = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != result) {
                times--;
            } else {
                times++;
            }
            if (times == -1) {
                times = 1;
                result = nums[i];
            }
        }
        return result;
    }
}
